package dp;

/**
 * question: 求一个数组中，一个连续子数组，这个子数组的和最大
 * example: 所有正数连续的情况  [1,2,3,4,-10]  -> [1,2,3,4]
 * 所有正数不连续的情况         [1,2,-5, 6,7] -> [6,7]
 * 全为负数                  [-1,-2,-3] -> [-1]
 *
 * @author Liaorun
 */
public class SubArrayMaxSum {

    public static void main(String[] args) {
        System.out.println(maxSum(new int[]{-1, -2, -3}));
    }

    public static int maxSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        // 记录连续子数组的元素的最大和
        int max = Integer.MIN_VALUE;
        int cur = 0;

        for (int i : arr) {
            cur += i;

            // 检查是否可以刷新最好的情况
            max = Math.max(max, cur);

            // cur 变成负数，表示前面一段的连续子数组带了的收益为负
            // 最好的结果不能考虑前面的数字
            cur = Math.max(cur, 0);
        }

        return max;
    }
}
